Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid

This letter studies the problem of minimizing increasing set functions, equivalently, maximizing decreasing set functions, over the base matroid. This setting has received great interest, since it generalizes several applied problems including actuator and sensor placement problems in control, task allocation problems, video summarization, and many others. We study two greedy heuristics, namely, the forward and reverse greedy. We provide two novel performance guarantees for the approximate solutions obtained by them depending on both submodularity ratio and curvature.     

Conformational change-modulated spin transport at single-molecule level in carbon systems

Controlling the spin transport at the single-molecule level, especially without the use of ferromagnetic contacts, becomes a focus of research in spintronics. Inspired by the progress on atomic-level molecular synthesis, through first-principles calculations, we investigate the spin-dependent electronic transport of graphene nanoflakes with side-bonded functional groups, contacted by atomic carbon chain electrodes. It is found that, by rotating the functional group, the spin polarization of the transmission at the Fermi level could be switched between completely polarized and unpolarized states. Moreover, the transition between spin-up and spin-down polarized states can also be achieved, operating as a dual-spin filter. Further analysis shows that, it is the spin-dependent shift of density of states, caused by the rotation, that triggers the shift of transmission peaks, and then results in the variation of spin polarization. Such a feature is found to be robust to the length of the nanoflake and the electrode material, showing great application potential. Those findings may throw light on the development of spintronic devices.     

Group completion in the K-theory and Grothendieck–Witt theory of proto-exact categories

We study the algebraic K-theory and Grothendieck–Witt theory of proto-exact categories, with a particular focus on classes of examples of ${\mathbb{F}}_1$-linear nature. Our main results are analogues of theorems of Quillen and Schlichting, relating the K-theory or Grothendieck–Witt theory spaces of proto-exact categories defined using the (hermitian) Q-construction and group completion.     

Collective Strategy Condensation: When Envy Splits Societies

Human societies are characterized by three constituent features, besides others. (A) Options, as for jobs and societal positions, differ with respect to their associated monetary and non-monetary payoffs. (B) Competition leads to reduced payoffs when individuals compete for the same option as others. (C) People care about how they are doing relatively to others. The latter trait—the propensity to compare one’s own success with that of others—expresses itself as envy. It is shown that the combination of (A)–(C) leads to spontaneous class stratification. Societies of agents split endogenously into two social classes, an upper and a lower class, when envy becomes relevant. A comprehensive analysis of the Nash equilibria characterizing a basic reference game is presented. Class separation is due to the condensation of the strategies of lower-class agents, which play an identical mixed strategy. Upper-class agents do not condense, following individualist pure strategies. The model and results are size-consistent, holding for arbitrary large numbers of agents and options. Analytic results are confirmed by extensive numerical simulations. An analogy to interacting confined classical particles is discussed.     

Springer basic sets and modular Springer correspondence for classical types

We define the notion of basic set data for finite groups (building on the notion of basic set, but including an order on the irreducible characters as part of the structure), and we prove that the Springer correspondence provides basic set data for Weyl groups. Then we use this to determine explicitly the modular Springer correspondence for classical types (defined over a base field of odd characteristic $p$, and with coefficients in a field of odd characteristic $?\ne p$): the modular case is obtained as a restriction of the ordinary case to a basic set. In order to do so, we compare the order on bipartitions introduced by Dipper and James with the order induced by the Springer correspondence. We provide a quick proof, by sorting characters according to the dimension of the corresponding Springer fibre, an invariant which is directly computable from symbols.